package dfs;
/**
 * 给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。
 * https://leetcode-cn.com/problems/combination-sum-iv/
 *
 * @author: luo
 * @email: luo@nyist.edu.cn
 * @date: 2021/1/28 17:34
 */
public class CombinationSum4 {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        int target = 35;
        System.out.println(combinationSum4(nums, target));;
    }
    public static int combinationSum4(int[] nums, int target) {
        int[] stack = new int[target + 1];
        stack[0] = 1;
        for(int i=0;i<target;i++){
            for(int num : nums){
                if(i + num <= target){
                    stack[i+num] += stack[i];
                }
            }
        }
        return stack[target];
    }
}
